1. Field of the Invention
The present invention generally relates to codes for correcting erasure errors and, more particularly, to constructing codes for which the encoding and correcting algorithms can be executed fast or “on-the-fly”. The invention has particular application in reading data from arrays of hard disks in data processing systems.
2. Background Description
In some applications, for example in RAID (Redundant Array of Inexpensive (or Independent) Disks) systems, it is necessary to construct codes for correcting erasure errors; i.e., errors whose location is known. It is also desirable that both the encoding and the correcting algorithms be executed fast. The usual encoding and correcting algorithms operate on bytes (or as many bits as the dimension of the field), and thus require the breaking of the stream of data into small chunks plus special circuitry to perform the field operations. This is time consuming when done on a general purpose microprocessor, and therefore specially designed chips, such as ASICs (Application Specific Integrated Circuits), are used for the execution of these algorithms.
Storage systems have relied on simple erasure codes (e.g., parity, mirroring, etc.) to protect against data loss. However, disk drive reliability has not increased as fast as the drive capacity has increased, creating significant vulnerabilities for simple codes. The industry-wide shift to SATA (Serial Advanced Technology Attachment) based hard disk drives (HDDs) will make this more of an issue. Therefore, significantly stronger erasure codes are going to be required for storage systems.
It is known that Reed-Solomon (RS) coding is used in RAID systems. See, for example, the article by James S. Plank entitled “A tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems”, Software-Practice and Experience, Vol. 27(9), September 1997, pp. 995–1012. The author describes a three data, three check arrangement as an example of how to produce RS encoding and decoding. He shows how to generate the appropriate Vandermonde matrix, how to use it to generate three checks, and then how to use it to decode from three devices. However, the author states on page 1008: “To the author's knowledge, there is no parity-based scheme that tolerates three or more device failures with minimal device overhead.”
It is highly desirable to have the encoding process be as efficient as possible, both in terms of operation per data byte transferred and required memory operations. Ideal solutions would rely only on exclusive OR (XOR) operations, with no branching. The EVENODD code is one such code, but it has some significant limitations. First, there are known solutions only up to distance four. Second, the size of a data set on a drive must be a multiple of a prime number minus one, and the number of data drives must also be less the prime number. The result is a rather inflexible code, and usually requires operating a rather large data set, since 3, 5 and 17 are the only small primes where the prime equals 2n+1, allowing standard length data sectors. The data operations are performed by mixing data words from (prime minus one) locations on each data drive, necessitating a large register set or many memory operations.
U.S. Pat. No. 5,271,012 to Blaum et al. discloses a method for encoding and rebuilding the data contents of up to two unavailable direct access storage devices (DASDs) in a DASD array. This method uses an example of the EVENODD code described above. Also relevant are U.S. Pat. No. 5,33,143 and No. 5,579,475, both to Blaum et al., which disclose similar methods for coding and rebuilding data from up to two unavailable DASDs in a DASD array.